package util.preprocessing;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.LinkedList;

import util.string.StringAnalysis;

public class QuerySelection {

	static final int QUERY_POS = 2;
	static final int SESSION_POS = 1;
	static final int URL_POS = 5;
	static final int NEW_QUERY = 0;
	static final int WORD_ADDED = 1;
	static final int WORD_REMOVED = 2;
	static final int WORD_CHANGED = 3;
	static final int MORE_RESULTS = 4;
	static final int PREVIOUS_QUERY = 5;
	static final int END_SESSION = 6;

	static final int EDIT_THRESHOLD = 2;

	static final int ERROR = -1;

	/**
	 * Returns true if at least 1 word was added to the previous query at
	 * position pos of the session
	 * 
	 */
	public static boolean wordAdded(LinkedList<String[]> session, int pos) {

		String previous_query[] = session.get(pos - 1);
		String current_query[] = session.get(pos);

		if (current_query[QUERY_POS].startsWith(previous_query[QUERY_POS]) &&

		!current_query[QUERY_POS].equals(previous_query[QUERY_POS])) {
			return true;

		}

		return false;
	}

	private static boolean wordAdded(String[] queryA, String[] queryB) {
		// TODO Auto-generated method stub

		LinkedList<String[]> miniSession = new LinkedList<String[]>();

		miniSession.addLast(queryA);
		miniSession.addLast(queryB);

		return wordAdded(miniSession, miniSession.size() - 1);

	}

	/**
	 * Returns true if at least 1 word was removed to the previous query at
	 * position pos of the session
	 * 
	 */
	public static boolean wordRemoved(LinkedList<String[]> session, int pos) {

		String previous_query[] = session.get(pos - 1);
		String current_query[] = session.get(pos);

		if (previous_query[QUERY_POS].startsWith(current_query[QUERY_POS]) &&

		!current_query[QUERY_POS].equals(previous_query[QUERY_POS])) {
			return true;
		}

		return false;
	}

	public static boolean isNewQuery(LinkedList<String[]> session, int pos) {

		if (pos == 0)
			return true;

		String previous_query[] = session.get(pos - 1);
		String current_query[] = session.get(pos);

		String a[] = previous_query[QUERY_POS].split("\\s+");
		String b[] = current_query[QUERY_POS].split("\\s+");

		for (int i = 0; i < a.length; i++) {

			for (int j = 0; j < b.length; j++) {

				if (a[i].trim().equals(b[j].trim())) {

					return false;
				}

			}
		}

		return true;

	}

	public static LinkedList<LinkedList<String[]>> getGoalsPerSession(
			LinkedList<String[]> session) {

		LinkedList<LinkedList<String[]>> goals = new LinkedList<LinkedList<String[]>>();

		Hashtable<Integer, HashSet<Integer>> goals_index = new Hashtable<Integer, HashSet<Integer>>();
		Hashtable<Integer, HashSet<Integer>> index_inverted = new Hashtable<Integer, HashSet<Integer>>();

		for (int i = 0; i < session.size(); i++) {

			Integer i_index = new Integer(i);
			HashSet<Integer> set = new HashSet<Integer>();

			goals_index.put(i_index, set);

			for (int j = i + 1; j < session.size(); j++) {

				if (areQueriesOnTheSameGoal(session.get(i), session.get(j))) {

					Integer j_index = new Integer(j);
					/*
					 * System.out.println(i_index + "\t" + j_index + "\t" +
					 * session.get(i)[QUERY_POS] + "\t" +
					 * session.get(j)[QUERY_POS]);
					 */

					goals_index.get(i_index).add(j_index);

					if (index_inverted.containsKey(j_index)) {
						index_inverted.get(j_index).add(i_index);

					} else {
						HashSet<Integer> setI = new HashSet<Integer>();
						setI.add(i_index);
						index_inverted.put(j_index, setI);
					}

				} else {

					if (!index_inverted.containsKey(j)) {

						HashSet<Integer> setI = new HashSet<Integer>();

						index_inverted.put(j, setI);
					}
				}

			}
		}

		goals = getMergedGoals(goals_index, index_inverted, session);

		return goals;

	}
	
	
	

	/**
	 * Evaluate if two queries are part of the same user 'goal'
	 * 
	 * @param queryA
	 * @param queryB
	 * @return
	 */
	public static boolean areQueriesOnTheSameGoal(String[] queryA,
			String[] queryB) {

		String queryA_eval[] = new String[queryA.length];
		for (int i = 0; i < queryA.length; i++) {
			queryA_eval[i] = queryA[i];

		}

		queryA_eval[QUERY_POS] = StringAnalysis
				.queryEntryNormalization(queryA[QUERY_POS]);

		String queryB_eval[] = new String[queryB.length];
		for (int i = 0; i < queryB.length; i++) {

			queryB_eval[i] = queryB[i];

		}

		queryB_eval[QUERY_POS] = StringAnalysis
				.queryEntryNormalization(queryB[QUERY_POS]);

		int state = evaluateCurrentQuery(queryA_eval, queryB_eval);

		int edit_distance = StringAnalysis.getEditDistance(
				queryA_eval[QUERY_POS].replaceAll(" ", ""),
				queryB_eval[QUERY_POS].replaceAll(" ", ""));

		if (state == WORD_REMOVED || state == WORD_CHANGED
				|| state == MORE_RESULTS || state == WORD_ADDED)
			return true;

		// revise this -----------------------------------
		if (queryA_eval.length > URL_POS && queryB_eval.length > URL_POS) {

			if (queryA_eval[URL_POS].trim().equals(queryB_eval[URL_POS])) {

				return true;
			}
		}

		if (edit_distance <= EDIT_THRESHOLD) {
			return true;

		}

		return false;
	}

	public static boolean moreResultsSameQuery(LinkedList<String[]> session,
			int pos) {

		if (pos == 0)
			return false;

		String previous_query[] = session.get(pos - 1);
		String current_query[] = session.get(pos);

		if (current_query[QUERY_POS].equals(previous_query[QUERY_POS])) {
			return true;
		}

		return false;

	}

	public static boolean returnToPreviousQuery(LinkedList<String[]> session,
			int pos, Hashtable<String, HashSet<Integer>> query_pos) {

		if (pos < session.size() && pos > 1) {

			String current = session.get(pos)[QUERY_POS].trim();
			HashSet<Integer> previous_queries = query_pos.get(current);

			Iterator<Integer> iter = previous_queries.iterator();

			while (iter.hasNext()) {

				Integer i = iter.next();
				if (i < pos - 1) {

					return true;

				}

			}

		}

		return false;

	}

	public static int evaluateCurrentQuery(
			Hashtable<String, HashSet<Integer>> query_pos,
			LinkedList<String[]> session, int pos) {

		if (pos < session.size()) {

			if (moreResultsSameQuery(session, pos)) {

				return MORE_RESULTS;

			}

			else if (returnToPreviousQuery(session, pos, query_pos)) {

				return PREVIOUS_QUERY;

			}

			else if (isNewQuery(session, pos)) {
				return NEW_QUERY;
			}

			else if (wordAdded(session, pos)) {

				return WORD_ADDED;
			} else if (wordRemoved(session, pos)) {
				return WORD_REMOVED;

			} else if (changedWordsInQuery(session, pos)) {

				return WORD_CHANGED;
			} else {

				return ERROR;
			}

		} else {
			return END_SESSION;

		}
	}

	public static boolean changedWordsInQuery(LinkedList<String[]> session,
			int pos) {

		String previous_query[] = session.get(pos - 1);
		String current_query[] = session.get(pos);

		String a[] = previous_query[QUERY_POS].split("\\s+");
		String b[] = current_query[QUERY_POS].split("\\s+");

		for (int i = 0; i < b.length; i++) {

			for (int j = 0; j < a.length; j++) {

				if (b[i].trim().equals(a[j].trim())) {

					return true;
				}

			}
		}

		return false;

	}

	static LinkedList<LinkedList<String[]>> getMergedGoals(
			Hashtable<Integer, HashSet<Integer>> indexes,
			Hashtable<Integer, HashSet<Integer>> indexInverted,
			LinkedList<String[]> session) {

		LinkedList<LinkedList<String[]>> goals = new LinkedList<LinkedList<String[]>>();

		Hashtable<Integer, HashSet<Integer>> merged_indexes = mergeGoalSets(
				indexes, indexInverted);

		Integer[] keys = (Integer[]) merged_indexes.keySet().toArray(
				new Integer[0]);
		Arrays.sort(keys);

		for (int i = 0; i < keys.length; i++) {

			Integer key = keys[i];
			HashSet<Integer> members = merged_indexes.get(key);

			Integer[] members_array = (Integer[]) members
					.toArray(new Integer[0]);
			Arrays.sort(members_array);

			LinkedList<String[]> list = new LinkedList<String[]>();
			// list.add(session.get(key));

			for (int j = 0; j < members_array.length; j++) {

				Integer member = members_array[j];

				list.add(session.get(member));

			}

			goals.add(list);

		}
		return goals;

	}

	static Hashtable<Integer, HashSet<Integer>> mergeGoalSets(
			Hashtable<Integer, HashSet<Integer>> indexes,
			Hashtable<Integer, HashSet<Integer>> indexInverted) {

		Integer[] keys = (Integer[]) indexes.keySet().toArray(new Integer[0]);
		Arrays.sort(keys);

		HashSet<Integer> temporal = new HashSet<Integer>();

		Hashtable<Integer, HashSet<Integer>> indexes_merged = new Hashtable<Integer, HashSet<Integer>>();

		for (int i = 0; i < keys.length; i++) {

			Integer current = keys[i];

			if (!temporal.contains(current)) {
				temporal.add(current);
				HashSet<Integer> merged = new HashSet<Integer>();
				mergeHelper(current, indexes, indexInverted, temporal, merged);
				temporal.addAll(merged);
				merged.add(current);

				indexes_merged.put(current, merged);

			}

		}
		return indexes_merged;
	}

	private static void traceBack(
			Hashtable<Integer, HashSet<Integer>> indexInverted,
			HashSet<Integer> merged, Integer current,
			HashSet<Integer> temporal_back) {
		// TODO Auto-generated method stub

		if (!indexInverted.containsKey(current))
			return;

		Iterator<Integer> indexes = indexInverted.get(current).iterator();

		while (indexes.hasNext()) {
			Integer back = indexes.next();

			if (!temporal_back.contains(back)) {

				temporal_back.add(back);

				merged.add(back);
				traceBack(indexInverted, merged, back, temporal_back);

			}

		}

	}

	private static void mergeHelper(Integer current,
			Hashtable<Integer, HashSet<Integer>> indexes,
			Hashtable<Integer, HashSet<Integer>> indexInverted,
			HashSet<Integer> temporal, HashSet<Integer> merged) {

		// TODO Auto-generated method stub

		HashSet<Integer> set = indexes.get(current);
		HashSet<Integer> temporal_back = new HashSet<Integer>();
		Iterator<Integer> iter = set.iterator();

		while (iter.hasNext()) {

			Integer next = iter.next();

			if (!temporal.contains(next)) {

				merged.add(next);
				mergeHelper(next, indexes, indexInverted, temporal, merged);
				traceBack(indexInverted, merged, current, temporal_back);

				temporal.add(next);
			}

		}

	}

	private static boolean isNewQuery(String[] queryA, String[] queryB) {
		// TODO Auto-generated method stub

		LinkedList<String[]> miniSession = new LinkedList<String[]>();

		miniSession.addLast(queryA);
		miniSession.addLast(queryB);

		return isNewQuery(miniSession, miniSession.size() - 1);

	}

	private static boolean changedWordsInQuery(String[] queryA, String[] queryB) {
		// TODO Auto-generated method stub

		LinkedList<String[]> miniSession = new LinkedList<String[]>();

		miniSession.addLast(queryA);
		miniSession.addLast(queryB);

		return changedWordsInQuery(miniSession, miniSession.size() - 1);

	}

	private static boolean wordRemoved(String[] queryA, String[] queryB) {
		// TODO Auto-generated method stub
		LinkedList<String[]> miniSession = new LinkedList<String[]>();

		miniSession.addLast(queryA);
		miniSession.addLast(queryB);

		return wordRemoved(miniSession, miniSession.size() - 1);
	}

	private static boolean moreResultsSameQuery(String[] queryA, String[] queryB) {
		// TODO Auto-generated method stub

		LinkedList<String[]> miniSession = new LinkedList<String[]>();

		miniSession.addLast(queryA);
		miniSession.addLast(queryB);

		return moreResultsSameQuery(miniSession, miniSession.size() - 1);
	}

	public static int evaluateCurrentQuery(String[] queryA, String[] queryB) {

		if (moreResultsSameQuery(queryA, queryB)) {

			return MORE_RESULTS;

		}

		else if (isNewQuery(queryA, queryB)) {
			return NEW_QUERY;
		}

		else if (wordAdded(queryA, queryB)) {

			return WORD_ADDED;
		} else if (wordRemoved(queryA, queryB)) {
			return WORD_REMOVED;

		} else if (changedWordsInQuery(queryA, queryB)) {

			return WORD_CHANGED;
		} else {

			return ERROR;
		}

	}

}
